package com.lsa.letcode.the67.addBinary;

public class Solution {
    public String addBinary(String a, String b) {
    	CharBuffer r = new CharBuffer('0', Math.max(a.length(), b.length()) + 1);
    	add(a, b, r);
    	return trimLeadingZeroes(r).toString();
    }
    
    void add(CharSequence num1, CharSequence num2, CharBuffer r) {
    	if (num1.length() < num2.length()) {
    		CharSequence t = num1;
    		num1 = num2;
    		num2 = t;
    	}
    	
		int lenDiff = num1.length() - num2.length();
		int carry = 0;
		int rIdx = r.length();
		for (int i = num1.length() - 1; i > -1 ; --i) {
			int n1 = num(num1.charAt(i));
			int j = i - lenDiff;
			int n2 = 0;
			if (j > - 1) {
				n2 = num(num2.charAt(j));
			}
			int t = n1 + n2 + carry;
			int d = t % 2;
			r.charAt(--rIdx, chr(d));
			carry = t / 2;
		}
		
		if (carry != 0) {
			r.charAt(--rIdx, chr(carry));
		}
    }
    
    static CharBuffer trimLeadingZeroes(CharBuffer r) {
		int i = 0;
    	for (;i < r.length(); i++) {
    		if (r.charAt(i) != '0') {
    			break;
    		}
		}
    	if (i < r.length()) {
    		return r.subSequence(i, r.length());
    	}
    	else {
    		return new CharBuffer("0");
    	}
	}
    
    static class CharBuffer implements CharSequence {
    	private final char[] chars;
		private final int from;
		private final int to;
		
		public CharBuffer(char c, int length) {
			chars = new char[length];
			for (int i = 0; i < length; i++) {
				chars[i] = c;
			}
			from = 0;
			to = length;
		}
		
		public CharBuffer(String s) {
			this(s.toCharArray(), 0, s.length());
		}
    	
		public CharBuffer(char[] chars, int from, int to) {
			if (from < 0 || from >= chars.length || to < 0 || to > chars.length || from > to) {
				throw new IndexOutOfBoundsException();
			}
			this.chars = chars;
			this.from = from;
			this.to = to;
		}
		
		public char[] getChars() {
			return chars;
		}

		public void setChars(char c) {
			for (int i = from; i < to; i++) {
				chars[i] = c;
			}
		}
		
		@Override
		public int length() {
			return to - from;
		}

		@Override
		public char charAt(int index) {
			if (from + index < 0 || from + index >= to) {
				throw new IndexOutOfBoundsException();
			}
			return chars[from + index];
		}
		
		public void charAt(int index, char c) {
			if (from + index < 0 || from + index >= to) {
				throw new IndexOutOfBoundsException();
			}
			chars[from + index] = c;
		}

		@Override
		public CharBuffer subSequence(int start, int end) {
			return new CharBuffer(chars, from + start, from + end);
		}

		@Override
		public String toString() {
			return new String(chars, from, to - from);
		}
    }
    
    int num(char c) {
    	return c - '0';
    }
    
    char chr(int n) {
    	return (char)('0' + n);
    }
}